#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <assert.h>
#include <malloc.h>
#include <stdlib.h>

typedef int DataType;
typedef struct SLinkList {
	DataType data;
	struct SLinkList* next;
}list;

void SLinkList_PushBack(list* phead, DataType x)
{
	list* tail = phead;
	list* node = (list*)malloc(sizeof(list));
	node->data = x;
	node->next = NULL;
	while (tail->next)
	{
		tail = tail->next;
	}
	tail->next = node;
}
void SLinkList_Print(list* phead)
{
	assert(phead);
	list* cur = phead->next;
	while (cur)
	{
		printf("%d -> ", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

void SLinkList_merge(list* phead1, list* phead2, list* phead3)
{
	assert(phead1 && phead2 && phead3);
	list* cur1 = phead1->next;
	list* cur2 = phead2->next;
	list* c1 = cur1->next;
	list* c2 = cur2->next;
	while (cur1 != NULL && cur2 != NULL)
	{
		if (cur1->data > cur2->data )
		{
			cur2->next = phead3->next;
			phead3->next = cur2;
			cur2= c2;
			if (c2 != NULL)
			{
				c2 = c2->next;

			}
			
		}
		else
		{
			cur1->next = phead3->next;
			phead3->next = cur1;
			cur1 = c1;
			if (c1 != NULL)
			{
				c1 = c1->next;

			}
		}
	}
	while (cur1)
	{
		cur1->next = phead3->next;
		phead3->next = cur1;
		cur1 = c1;
		if (c1 != NULL)
		{
			c1 = c1->next;
		}
	}
	while (cur2)
	{
		cur2->next = phead3->next;
		phead3->next = cur2;
		cur2 = c2;
		if (c2 != NULL)
		{
			c2 = c2->next;
		}
	}
}



//int main()
//{
//	list head;
//	head.data = -1;
//	head.next = NULL;
//	list head2;
//	head2.data = -1;
//	head2.next = NULL;
//	list head3;
//	head3.data = -1;
//	head3.next = NULL;
//	SLinkList_PushBack(&head, 1);
//	SLinkList_PushBack(&head, 3);
//	SLinkList_PushBack(&head, 5);
//	SLinkList_PushBack(&head, 7);
//	SLinkList_PushBack(&head, 9);
//	SLinkList_Print(&head);
//
//	SLinkList_PushBack(&head2, 2);
//	SLinkList_PushBack(&head2, 4);
//	SLinkList_PushBack(&head2, 6);
//	SLinkList_PushBack(&head2, 8);
//	SLinkList_PushBack(&head2, 10);
//	SLinkList_Print(&head2);
//
//	SLinkList_merge(&head, &head2, &head3);
//	SLinkList_Print(&head3);
//
//	return 0;
//}